from typing import List


class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        size = len(word)

        for i0 in range(m):
            for j0 in range(n):
                # 从上向下
                if (i0 + size <= m
                        and (i0 == 0 or board[i0 - 1][j0] == "#")
                        and (i0 + size == m or board[i0 + size][j0] == "#")):
                    for i1 in range(size):
                        if board[i0 + i1][j0] == "#":
                            break
                        if board[i0 + i1][j0].isalpha() and board[i0 + i1][j0] != word[i1]:
                            break
                    else:
                        # print('从上向下:', (i0, j0))
                        return True

                # 从下向上
                if (i0 - size >= -1
                        and (i0 == m - 1 or board[i0 + 1][j0] == "#")
                        and (i0 - size == -1 or board[i0 - size][j0] == "#")):
                    for i1 in range(size):
                        if board[i0 - i1][j0] == "#":
                            break
                        if board[i0 - i1][j0].isalpha() and board[i0 - i1][j0] != word[i1]:
                            break
                    else:
                        # print('从下向上:', (i0, j0))
                        return True

                # 从左向右
                if (j0 + size <= n
                        and (j0 == 0 or board[i0][j0 - 1] == "#")
                        and (j0 + size == n or board[i0][j0 + size] == "#")):
                    for j1 in range(size):
                        if board[i0][j0 + j1] == "#":
                            break
                        if board[i0][j0 + j1].isalpha() and board[i0][j0 + j1] != word[j1]:
                            break
                    else:
                        # print('从左向右:', (i0, j0))
                        return True

                # 从右向左
                if (j0 - size >= -1
                        and (j0 == n - 1 or board[i0][j0 + 1] == "#")
                        and (j0 - size == -1 or board[i0][j0 - size] == "#")):
                    for j1 in range(size):
                        if board[i0][j0 - j1] == "#":
                            break
                        if board[i0][j0 - j1].isalpha() and board[i0][j0 - j1] != word[j1]:
                            break
                    else:
                        # print('从右向左:', (i0, j0))
                        return True

        return False


if __name__ == "__main__":
    # True
    print(Solution().placeWordInCrossword(board=[["#", " ", "#"],
                                                 [" ", " ", "#"],
                                                 ["#", "c", " "]],
                                          word="abc"))

    # False
    print(Solution().placeWordInCrossword(board=[[" ", "#", "a"],
                                                 [" ", "#", "c"],
                                                 [" ", "#", "a"]],
                                          word="ac"))

    # True
    print(Solution().placeWordInCrossword(board=[["#", " ", "#"],
                                                 [" ", " ", "#"],
                                                 ["#", " ", "c"]],
                                          word="ca"))
